package com.Algorithm;

import java.util.Arrays;

/**
 * 堆排序
 *
 * @author yisl
 * @create 2019-07-01 16:22
 */
public class HeapSort {

    /**
    * @Description:
     * 对简单选择排序的优化。
     * 将序列构建成大顶堆。
     *
     * 将根节点与最后一个节点交换，然后断开最后一个节点。
     *
     * 重复第一、二步，直到所有节点断开
    * @Param: [a]
    * @return: void
    * @Author: yisl
    * @Date: 2019-07-01
    */
    public static void heapSort(int[] a) {

        for (int i = 0; i < a.length -1; i++){


            //构建大顶堆
            buildMaxHeap(a, a.length - 1 - i);

            //将根节点与最后一个节点交换
            swap(a,0, a.length - i -1);

            System.out.println(Arrays.toString(a));

        }



    }

    public static void buildMaxHeap(int[] a, int lastIndex) {

        for (int i = (a.length -1)/2; i>=0; i--){

            int k = i;
            while (k*2+1<=lastIndex){

                int biggerIndex = k*2 + 1;

                if (biggerIndex < lastIndex){
                    if (a[biggerIndex] < a[biggerIndex+1]){
                        biggerIndex++;
                    }
                }

                if (a[k] < a[biggerIndex]){
                    swap(a, k, biggerIndex);
                    k = biggerIndex;
                }else {
                    break;
                }
            }

        }

    }

    public static void buildMaxHeap1(int[] a, int index){
        for (int i = (a.length -1)/2; i >=0; i--) {
            int k=i;
            while (2*k+1<=index){
                int bigger = 2*k+1;
                if (bigger<index){
                    if (a[bigger]<a[bigger+1]){
                        bigger++;
                    }
                }

                if (a[k]<a[bigger]){
                    swap(a, k, bigger);
                    k=bigger;
                }else{
                    break;
                }
            }
        }

    }


    public static void heapSort1(int[] a){

        for (int i = 0; i < a.length; i++) {
            buildMaxHeap1(a, a.length - i -1);
            swap(a, 0, a.length - i -1);
        }
    }



    public static void swap(int[] a, int i, int j){
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }

    public static void main(String[] args) {
        int[] a = {32,43,23,13,5};
        //heapSort(a);
        heapsor2(a);
        System.out.println(Arrays.toString(a));

    }

    public static void heapsor2(int[] a){
        for (int i = 0; i < a.length; i++) {
            buildMaxHeap2(a, a.length-1-i);
            swap(a, 0, a.length-1-i);
        }
    }
    public static void buildMaxHeap2(int[] a, int index){
        for (int i = (a.length-1)/2; i >=0; i--) {
            int k = i;
            while (2*k+1<=index){
                int bigger = 2*k+1;
                if (bigger<index){
                    if(a[bigger] < a[bigger+1]){
                        bigger++;
                    }
                }

                if (a[k]<a[bigger]){
                    swap(a, k, bigger);
                    k=bigger;
                }else{
                    break;
                }
            }

        }
    }
}
